package Top200;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author zhangmin
 * @create 2022-02-26 16:17
 */
public class subsetsWithDup90 {
    List<List<Integer>> res=new LinkedList<>();
    void backtrack(int[] nums,int index,LinkedList<Integer> path,boolean ischoosed){
        if (index==nums.length){
            res.add(new LinkedList<>(path));
            return;
        }
        //选择当前path不要index元素
        backtrack(nums,index+1,path,false);
        if (!ischoosed&&index>0&&nums[index-1]==nums[index]){
            //排除重复路径
            return;
        }
        //选择要index元素
        path.add(nums[index]);
        backtrack(nums,index+1,path,true);
        path.removeLast();
    }
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        backtrack(nums,0,new LinkedList<>(),false);
        return res;
    }
}
